#include <queue>
#include <vector>

using namespace std;

/**
 * @brief 695. 岛屿的最大面积
 * https://leetcode.cn/problems/max-area-of-island/
 */
class Solution {
public:
    // DFS 解法
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int nr = grid.size();
        int nc = grid[0].size();
        int maxSoFar = 0;
        for (int i = 0; i < nr; i++) {
            for (int j = 0; j < nc; j++) {
                if (grid[i][j] == 1) {
                    int area = 0;
                    DFS(grid, i, j, area);
                    maxSoFar = max(maxSoFar, area);
                }
            }
        }
        return maxSoFar;
    }

    void DFS(vector<vector<int>>& grid, int i, int j, int& area) {
        area += 1;
        grid[i][j] = 0; // set to 0 when visited
        int nr = grid.size();
        int nc = grid[0].size();
        if (i-1 >= 0 && grid[i-1][j] == 1) DFS(grid, i-1, j, area);
        if (i+1 < nr && grid[i+1][j] == 1) DFS(grid, i+1, j, area);
        if (j-1 >= 0 && grid[i][j-1] == 1) DFS(grid, i, j-1, area);
        if (j+1 < nc && grid[i][j+1] == 1) DFS(grid, i, j+1, area);
    }

    /////////////////////////////////////////////////////////////////////
    // BFS 解法
    // 其实思路与 BFS 相同，注意 if (!grid[r][c]) continue; 这一行：
    // 如果缺少这一行，那么在如下例子中：
    //     1 1 0 0
    //     1 1 0 0
    // 右下角的 1 会被加入 queue 中两次；第二次出 queue 时即使已经被置为 0，
    // 但还是会增加面积！
    int maxAreaOfIsland_BFS(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m==0) return 0;
        int n = grid[0].size();

        int max_area = 0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    int curr_area = 0;
                    
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    while (!q.empty()) {
                        pair<int, int> pos = q.front(); q.pop();
                        int r = get<0>(pos), c = get<1>(pos);
                        if (!grid[r][c]) continue;  //! 关键行，相当于 DFS 中 if (!grid[r][c] == 1) return;
                        curr_area++;
                        grid[r][c] = 0;
                        if (r-1>=0 && grid[r-1][c]==1) q.push({r-1, c});
                        if (r+1< m && grid[r+1][c]==1) q.push({r+1, c});
                        if (c-1>=0 && grid[r][c-1]==1) q.push({r, c-1});
                        if (c+1< n && grid[r][c+1]==1) q.push({r, c+1});
                    }

                    max_area = max(max_area, curr_area);
                }
            }
        }

        return max_area;
    }
};
